
#include <xbi/xbixfselement.h>

#if 0
#pragma mark Definitions
#endif

#define _XBIXFSElementBufferSize (256+0xE)

#define _XBIXFSFileSystemSeparator '/'
#define _XBIXFSFileSystemSeparatorLength 1

static char * _XBIXFSRootElementName = "XboxFS";
static byte_t _XBIXFSRootElementNameLength = 6;

struct _XBIXFSElement {
    // B-Tree in the Xbox File System
    uint16_t leftOffset;
    uint16_t rightOffset;
    
    XBIXFSElement * parent;
    
    XBIXFSElement * * children;
    int numOfChildren;
    
    char *   name;
    byte_t   nameLength;    
    uint32_t length;
    int32_t  startSector;
    byte_t   attributes;
};

#if 0
#pragma mark Private functions
#endif

static void _XBIXFSElementLog(XBIXFSElement * element, int level) {
    int i;
    if (element == NULL || element->name == NULL)
        return;
    for (i=0; i<level; i++)
        XBILog("| "); // Simple indentation
    XBILog("+ %s\n", element->name);
    if (element->numOfChildren != 0)
        XBIAssert(element->children != NULL, "Children, but NULL array\n");
    if (element->children != NULL) {
        for (i=0; i<element->numOfChildren; i++) {
            XBIAssert(element->children != NULL, "Inconsistency : numOfChildren > 0 but children == NULL\n");
            XBIAssert(element->children[i] != NULL, "Inconsistency : children NULL at index < numOfChildren\n");
            _XBIXFSElementLog(element->children[i], level+1);
        }
    }
}

static void _XBIXFSElementAddChild(XBIXFSElement * element, XBIXFSElement * child, XBIError * error) {
    XBIXFSElement * * newChildren = NULL;
    if (element != NULL && child != NULL) {
        newChildren = realloc(element->children, sizeof(XBIXFSElement) * (element->numOfChildren + 1));
        if (newChildren == NULL) {
            // realloc says element->children is still ok, though
            *error = kXBINotEnoughMemory;
            return;            
        }
        element->children = newChildren;
        element->children[element->numOfChildren] = child;
        element->numOfChildren++;
//        XBILog("%s contains %s (%dth child)\n", element->name, child->name, element->numOfChildren);
        child->parent = element; // Store link back to the parent as well
    }
}

static XBIXFSElement * _XBIXFSElementCreateEmptyElement(XBIError * error) {
    XBIXFSElement * newElement;
    newElement = malloc(sizeof(XBIXFSElement));    
    if (newElement == NULL) {
        *error = kXBINotEnoughMemory;
        goto error;
    }
    memset(newElement, 0, sizeof(XBIXFSElement));
    return newElement;
error:
    return NULL;
}

static XBIXFSElement * _XBIXFSElementCreateFromBuffer(byte_t * buffer, size_t length, XBIError * error) {
    //    XBIAssert(length >= _XBIXFSElementBufferSize, "Creating from too small buffer - not really, though");
    XBIXFSElement * newElement = NULL;
    
    newElement = _XBIXFSElementCreateEmptyElement(error);    
    if (newElement == NULL) {
        *error = kXBINotEnoughMemory;
        goto error;
    }
    
    newElement->leftOffset =  XBIReadLittleEndianUInt16AtAddress(buffer);
    newElement->rightOffset = XBIReadLittleEndianUInt16AtAddress(buffer + 0x2);
    
    newElement->startSector = XBIReadLittleEndianInt32AtAddress(buffer + 0x4);
    newElement->length =      XBIReadLittleEndianUInt32AtAddress(buffer + 0x8);
    newElement->attributes =  buffer[0xC];
    newElement->nameLength =  buffer[0xD];
    XBIAssert(0xE +  newElement->nameLength <= length, "Supplied buffer too small\n");
    newElement->name =        malloc(newElement->nameLength + 1);
    if (newElement->name == NULL) {
        *error = kXBINotEnoughMemory;
        goto error;
    }
    memcpy(newElement->name, buffer + 0xE, newElement->nameLength);
    newElement->name[newElement->nameLength] = 0; // Enforce NULL-termination
    
    // Sanity checks
    if (newElement->startSector == 0xffffffff) {
        XBILog("Invalid TOC entry - Ignoring\n");
        *error = kXBIFileWrongFormat;
        goto error;
    }
    
//    XBILog("New XFSElement :\n  - LeftOffset   : 0x%X\n  - RightOffset  : 0x%X\n  - Start Sector : 0x%X\n  - Length       : %u\n  - Attributes   : 0x%X\n  - Name      : \"%s\"[%d]\n", newElement->leftOffset, newElement->rightOffset, newElement->startSector, newElement->length, newElement->attributes, newElement->name, newElement->nameLength);
    
    return newElement;
    
error:
    XBIXFSElementDelete(newElement);
    return NULL;    
}

static XBIXFSElement * _XBIXFSElementCreateWithParent(XBIXFSElement * parent, FILE * file, off_t fileSystemPosition, off_t bTreeRootOffset, off_t offset, XBIError * error) {
    XBIXFSElement * newElement = NULL;
    byte_t buffer[_XBIXFSElementBufferSize];
    
    XBIXFSElement * leftElement = NULL;  // Left element in the B-TREE
    XBIXFSElement * subElement = NULL;   // Folders point to a new B-TREE
    XBIXFSElement * rightElement = NULL; // Right element in the B-TREE
    
//    XBILog("Parsing from 0x%qX\n", offset+fileSystemPosition+bTreeRootOffset);
    
    if (fseeko(file, fileSystemPosition + bTreeRootOffset + offset, SEEK_SET) != 0) {
        *error = kXBIFileIOError;
        goto error;
    }
    
    if (fread(buffer, _XBIXFSElementBufferSize, 1, file) != 1) {
        *error = kXBIFileIOError;
        goto error;
    }
    
    newElement = _XBIXFSElementCreateFromBuffer(buffer, _XBIXFSElementBufferSize, error);
    if (newElement == NULL)
        goto error;
        
    if (newElement->startSector == 0 || newElement->length == 0) {
        // Empty FS element, let's just ignore it
        goto error;
    }
    
    /* The Xbox FS uses a binary tree. Each "element", be it a folder or a file, has two pointer, to two other "elements" : leftElement, and rightElement
       This binary-tree has NOTHING to do with the actual filesystem hierarchy. It's just a way to store "elements" on the DVD
       For instance, one file A that would be in the same FileSystem folder as another B could very well be a children of A in the B-Tree
     
       If any of those "pointers" is zero, it means the tree has no further branch
     */
    
    if (newElement->leftOffset != 0) {
        // The offest are relative to the start of the current binary tree
        leftElement = _XBIXFSElementCreateWithParent(parent, file, fileSystemPosition, bTreeRootOffset, 4*(off_t)newElement->leftOffset, error);
    }
    
    /* When an element is actually a folder, it still has a pointer to two other elements, which are siblings (not sub-elements)
       However, its sub-folders (actually all the elements it contains) are within ANOTHER binary tree (with of course a similar structure)
     */
    
    if (XBIXFSElementIsFolder(newElement)) {
        // Fine, let's give a look at our OWN binary tree. It starts a the sector pointed by element->startSector
        subElement = _XBIXFSElementCreateWithParent(newElement, file, fileSystemPosition, (kXBIDVDSectorSize * (off_t)(newElement->startSector)), 0, error);
    }
    
    if (newElement->rightOffset != 0) {
        // The offest are relative to the start of the current binary tree
        rightElement = _XBIXFSElementCreateWithParent(parent, file, fileSystemPosition, bTreeRootOffset, 4*(off_t)newElement->rightOffset, error);    
    }

    _XBIXFSElementAddChild(parent, newElement, error);

    return newElement;
    
error:
    XBIXFSElementDelete(newElement);
    return NULL;    
}

static XBIXFSElement * _XBIXFSElementCreateRootElement(XBIError * error) {
    XBIXFSElement * newElement = NULL;
    newElement = _XBIXFSElementCreateEmptyElement(error);        
    if (newElement == NULL) {
        *error = kXBINotEnoughMemory;
        goto error;
    }
    
    newElement->name = _XBIXFSRootElementName;
    newElement->nameLength = _XBIXFSRootElementNameLength;
    
    return newElement;
    
error:
    XBIXFSElementDelete(newElement);
    return NULL;
}

#if 0
#pragma mark Creation - Copy - Deletion
#endif

XBIXFSElement * XBIXFSElementCreate(XBIImage * image, XBIError * error) {
    XBIXFSElement * rootElement = _XBIXFSElementCreateRootElement(error);
    _XBIXFSElementCreateWithParent(rootElement, XBIImageGetFilePointer(image), XBIImageGetDataPartitionOffset(image), XBIImageGetFileSystemRootOffset(image), 0, error);
    _XBIXFSElementLog(rootElement, 0);
    return rootElement;
}

XBIXFSElement * XBIXFSElementCopy(XBIXFSElement * element) {
    return element; // TODO: Implement copy
}

void XBIXFSElementDelete(XBIXFSElement * element) {
    int i = 0;
    
    if (element == NULL)
        return;
    
    if (element->children != NULL) {
        for (i = 0; i < element->numOfChildren; i++) {
            XBIXFSElementDelete(element->children[i]);
        }
    }
    
    if (element->name != NULL && element->name != _XBIXFSRootElementName)
        free(element->name);
    
    free(element);
}

#if 0
#pragma mark Data manipulation
#endif

int XBIXFSElementIsFolder(XBIXFSElement * element) {
    if (element == NULL)
        return -1;
    return (element->attributes == 0x10 || element->attributes == 0x30);    
}

XBIXFSElement * XBIXFSElementFindChildWithPath(XBIXFSElement * element, char * path, size_t pathLength) {
    int i = 0;
    XBIXFSElement * childResult = NULL;
    char * fsSeparatorPosition = NULL;
    char * rootPath = NULL;
    size_t rootPathLength = 0;
    char * childPath = NULL;
    size_t childPathLength = 0;
    
    if (element == NULL || path == NULL || pathLength == 0 || element->name == NULL)
        goto error;

    
//    XBILog("Searching for %s in %s\n", path, element->name);

    fsSeparatorPosition = strchr(path, _XBIXFSFileSystemSeparator);
    if (fsSeparatorPosition == NULL) {
        if (strncmp(element->name, path, pathLength) == 0 && pathLength == element->nameLength) {
            return element;
        }
        goto error;
    }
    childPath = fsSeparatorPosition + _XBIXFSFileSystemSeparatorLength;
    childPathLength = pathLength - (size_t)(childPath - path);
    rootPath = path;
    rootPathLength = (size_t)(fsSeparatorPosition - path);
    

    if (strncmp(element->name, rootPath, rootPathLength) == 0) {
        for (i=0; i<element->numOfChildren; i++) {
            XBIAssert(element->children != NULL, "Inconsistency : numOfChildren > 0 but children == NULL\n");
            XBIAssert(element->children[i] != NULL, "Inconsistency : children NULL at index < numOfChildren\n");
            childResult = XBIXFSElementFindChildWithPath(element->children[i], childPath, childPathLength);
            if (childResult != NULL)
                return childResult;
        }
    }
error:
    return NULL;
}

int XBIXFSElementCopyFullPath(XBIXFSElement * element, char * buffer, size_t bufferSize) {
    // Return value : number of bytes written
    int lengthOfParentPath = 0;
    if (element == NULL)
        goto error;
    
    if (element->nameLength + 1 > bufferSize) // Enforce NULL-termination in the buffer
        goto error;
    
    if (element->parent == NULL) // Don't include the Root node name
        goto error;
    
    lengthOfParentPath = XBIXFSElementCopyFullPath(element->parent, buffer, bufferSize);
    
    if (lengthOfParentPath + element->nameLength + 1 > bufferSize) // Enforce NULL-termination in the buffer
        goto error;
    
    strncpy(buffer+lengthOfParentPath, "/", 1);
    
    strncpy(buffer+1+lengthOfParentPath, element->name, element->nameLength);
    
    return lengthOfParentPath+1+element->nameLength;

error:
    return 0;
}

off_t XBIXFSElementGetStartByte(XBIXFSElement * element) {
    if (element != NULL)
        return kXBIDVDSectorSize * (off_t)element->startSector;
    return -1;
}

uint64_t XBIXFSElementGetSize(XBIXFSElement * element) {
    /* We're returning a 64bits value, even if the Xbox filesystem limits FS elements size to 32 bits */
    /* Indeed, a folder can contain several elements that add up to a value that would overflow 32 bits */
    uint64_t folderSize = 0;
    int i;
    
    if (element != NULL) {
        if (XBIXFSElementIsFolder(element)) {
            folderSize = 0;
            for (i=0; i<element->numOfChildren; i++) {
                XBIAssert(element->children != NULL, "Inconsistency : numOfChildren > 0 but children == NULL\n");
                XBIAssert(element->children[i] != NULL, "Inconsistency : children NULL at index < numOfChildren\n");
                folderSize += XBIXFSElementGetSize(element->children[i]);
            }
            return folderSize;
        } else
            return (uint64_t)element->length;        
    }
    return -1;    
}


#if 0
#pragma mark Accessors
#endif

char * XBIXFSElementGetName(XBIXFSElement * element) {
    if (element != NULL)
        return element->name;
    return NULL;
}

XBIXFSElement * XBIXFSElementGetChildrenAtIndex(XBIXFSElement * element, int index) {
    if (element != NULL) {
        XBIAssert(index < element->numOfChildren, "Accessing children at wrong index\n");
        return element->children[index];
    }
    return NULL;    
}

int XBIXFSElementGetNumberOfChildren(XBIXFSElement * element) {
    if (element != NULL)
        return element->numOfChildren;
    return -1;    
}
